package com.muchfish.algorithm.linkedlist;

import com.muchfish.algorithm.linkedlist.pojo.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/linked-list-cycle-ii/solutions/">题目：142. 环形链表Ⅱ</a>
 * <br>
 * 题目描述：
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。<br>
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，<br>
 * 评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。<br>
 * 不允许修改 链表。<br>
 * <br>
 * 解题思路： <br>
 * 1.哈希表法
 * <img src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png">
 * 1.1 遍历链表，将每个节点放入哈希表中
 * 1.2 如果当前节点已经存在于哈希表中，则说明当前节点是环形链表的入口节点，返回当前节点即可
 * 2.快慢指针法
 * <img src="https://assets.leetcode-cn.com/solution-static/142/142_fig1.png">
 * 2.1 初始化快慢指针，快指针一次走两步，慢指针一次走一步
 * 2.2 如果快慢指针不相遇，则说明链表不存在环，返回null
 * 2.3 如果快慢指针相遇，则说明链表存在环，返回相遇节点
 * 2.3.1 此时，快慢指针相遇，且慢指针已经在环内，那么我们需要找到环的入口节点，即相遇节点
 * 2.3.2
 *
 */
public class LinkedList3 {
    public static void main(String[] args) {
        System.out.println(detectCycle(new ListNode(3, new ListNode(2, new ListNode(0, new ListNode(-4, new ListNode(2)))))));
    }

    private static ListNode  detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;

    }

    private static ListNode  detectCycle1(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (!visited.add(pos)) {
                return pos;
            }
            pos = pos.next;
        }
        return null;
    }
}
